#    URLs: http://code.google.com/p/rmxp-export-import-utility/
#    Copyright (C) 2011, Raku, Zitak
#
#    This file is part of RXMP Plugin Utility.
#
#    RXMP Plugin Utility is free software: you can redistribute it and/or modify
#    it under the terms of the GNU General Public License as published by
#    the Free Software Foundation, either version 3 of the License, or
#    (at your option) any later version.
#
#    RXMP Plugin Utility is distributed in the hope that it will be useful,
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#    GNU General Public License for more details.
#
#    You should have received a copy of the GNU General Public License
#    along with RXMP Plugin Utility.  If not, see <http://www.gnu.org/licenses/>.
#
# mutable.rb

require File.dirname(__FILE__) + '/base'

module RGL

  # A MutableGraph can be changed via the addition or removal of edges and
  # vertices. 
  module MutableGraph

    include Graph

    # Add a new vertex _v_ to the graph.  If the vertex is already in the
    # graph (tested via eql?), the method does nothing.

    def add_vertex (v)
      raise NotImplementedError
    end

    # Inserts the edge (u,v) into the graph.
    #
    # Note that for undirected graphs, (u,v) is the same edge as (v,u), so
    # after a call to the function add_edge(), this implies that edge (u,v)
    # will appear in the out-edges of u and (u,v) (or equivalently (v,u))
    # will appear in the out-edges of v.  Put another way, v will be adjacent
    # to u and u will be adjacent to v. 

    def add_edge (u, v)
      raise NotImplementedError
    end

    # Add all objects in _a_ to the vertex set.

    def add_vertices (*a)
      a.each { |v| add_vertex v }
    end

    # Add all edges in the _edges_ array to the edge set.  Elements of the
    # array can be both two-element arrays or instances of DirectedEdge or
    # UnDirectedEdge. 

    def add_edges (*edges)
      edges.each { |edge| add_edge(edge[0], edge[1]) }
    end

    # Remove u from the vertex set of the graph.  All edges whose target is
    # _v_ are also removed from the edge set of the graph.
    #
    # Postcondition: num_vertices is one less, _v_ no longer appears in the
    # vertex set of the graph, and there no edge with source or target _v_.

    def remove_vertex (v)
      raise NotImplementedError
    end

    # Remove the edge (u,v) from the graph.  If the graph allows parallel
    # edges, this removes all occurrences of (u,v).
    # 
    # Precondition: u and v are vertices in the graph.
    # Postcondition: (u,v) is no longer in the edge set for g.

    def remove_edge (u, v)
      raise NotImplementedError
    end

    # Remove all vertices specified by the array a from the graph by calling
    # remove_vertex.

    def remove_vertices (*a)
      a.each { |v| remove_vertex v }
    end

    # Returns all minimum cycles that pass through a give vertex. 
    # The format is an Array of cycles, with each cycle being an Array
    # of vertices in the cycle.
    def cycles_with_vertex(vertex)
      cycles_with_vertex_helper(vertex, vertex, [])
    end

  protected
    def cycles_with_vertex_helper(vertex, start, visited) #:nodoc:
      adjacent_vertices(start).reject {|x| visited.include?(x)}.inject([]) do |acc, adj|
        local_visited = Array.new(visited) << adj
        acc << local_visited if (adj==vertex)
        acc = acc + cycles_with_vertex_helper(vertex,adj,local_visited)
      end
    end

  public
    # Returns an array of all minimum cycles in a graph
    #
    # This is not an efficient implementation O(n^4) and could
    # be done using Minimum Spanning Trees. Hint. Hint.
    def cycles
      g = self.clone
      self.inject([]) do |acc, v| 
        acc = acc.concat(g.cycles_with_vertex(v))
        g.remove_vertex(v); acc
      end
    end

  end		# module MutableGraph
end		# module RGL
